package com.fr.lintcode;

import org.junit.Test;

public class Q1666 {

    /**
     * @param a: the n numbers
     * @param k: the number of integers you can choose
     * @return: how many ways that the sum of the k integers is a prime number
     */
	int count = 0;
    public int getWays(int[] a, int k) {
        // Write your code here
    	if(a == null || a.length < k) {
    		return 0;
    	}
    	int length = a.length;
    	boolean []used = new boolean[length];
    	int index = -1;
    	int usedNum = 0;
    	search(a, used, index, usedNum, k);
    	return count;
    }
	private void search(int[] a, boolean[] used, int index, int usedNum, int k) {
		// TODO Auto-generated method stub
		if(usedNum == k) {
			int sum = 0;
			for(int i = 0; i < used.length; i++) {
				if(used[i]) {
					sum += a[i];
				}
			}
			for(int i =2;i<= Math.sqrt(sum); i++) {
				if(sum % i == 0) {
					return;
				}
			}
			count ++;
		}
		for(int i = index + 1 ; i < a.length; i++) {
			usedNum ++;
			used[i] = true;
			search(a, used, i, usedNum, k);
			used[i] = false;
			usedNum --;
		}
	}
	@Test
	public void testSearch() {
		int [] a = {3,9,23,12,34,65,32,19,81};
		int k = 4;
		System.out.println(getWays(a, k));
	}

}
